#include "leetcode_util.h"

// solution()

void helper(string s, int n, string pre_s, vector<string>& res) {
    if (s.empty()) return;
    if (s.size() < n) return;
    if (n == 1) {
        if (s[0] == '0' && s.size() > 1) { // 025 illegal
            return;
        }
        int s_i = atoi(s.c_str());
        if (s_i > 255 || s_i < 0) {
            return;
        }
        res.push_back(pre_s + "." + s);
    } else {
        if (!pre_s.empty()) {
            pre_s += ".";
        }
        if (s[0] == '0') {
            helper(s.substr(1), n-1, pre_s+"0", res);
        } else {
            int max_i = s.size() > 2 ? 3 : s.size();
            for (int i = 1; i <= max_i; ++i) { // 2.55*** or 25.*** or 255.***
                int _s_i = atoi(s.substr(0,i).c_str());
                if (_s_i <= 255) {
                    helper(s.substr(i), n-1, pre_s+s.substr(0,i), res);
                }
            }
        }
    }
}

vector<string> restoreIpAddresses(string s) {
    vector<string> result;
    helper(s, 4, "", result);
    return result;
}

void test(string s) {
    vector<string> res = restoreIpAddresses(s);
    for (auto _s : res) {
        printf("'%s'", _s.c_str());
        printf(" ");
    }
    printf("\n");
}


int main(int argc, char *argv[]) {
    test("25525511135");
    test("1111");
    test("0000");
    test("2736786374048");
}

